/**
 * Created With IntelliJ IDEA
 * Description:leetcode：142. 环形链表 II
 * <a href="https://leetcode.cn/problems/linked-list-cycle-ii/submissions/">...</a>
 * User: DELL
 * Data: 2023-01-08
 * Time: 9:59
 */

class ListNode {
    int val;
    ListNode next;
    public ListNode (int val) {
        this.val = val;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;//快指针每次走两个结点
        ListNode slow = head;//慢指针每次走一个结点
        //判断是否有环，若有环找到slow和fast的相交结点
        while(fast!=null && fast.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) {
                break;
            }
        }
        //无环的情况
        if(fast==null || fast.next==null) {
            return null;
        }
        //根据数学公式推导，fast和head每次均向前走一个结点，最终会相遇在入环的第一个结点
        while(head != fast) {
            head = head.next;
            fast = fast.next;
        }
        return head;
    }
}